The MVDR computation is a well known problem in, for example, the field of radar beamforming employing an array of receiver antennas. It is also relevant to other sensors such as sonar transducer arrays. In one aspect, it may be considered as the computation of the minimum output from an array of receivers for each of a number of array "look" directions subject to the array gain in the respective direction remaining constant. This is equivalent to combining the array output signals so that unwanted contributions received other than from the required direction tend to cancel out, while antenna array gain in the required direction is preserved. The MVDR problem relates to achieving this result for a plurality of directions simultaneously; i.e. array output signals are required to be processed to yield noise-reduced signals or residuals corresponding to a number of different "look" directions.
Mathematically, the MVDR problem may be described as follows. Consider an array of m receivers each producing successive output signals, the ith signal from the jth receiver being designated x.sub.ij (i=1,2,3 . . . , j=1 to m). An array of receivers is normally arranged to provide synchronous outputs, so the ith set of signals obtained from such an array at time t.sub.i consists of x.sub.i1 to x.sub.im. This signal set is treated as a row vector x.sup.T (t.sub.i), where the symbol T indicates the transpose of a column vector. Successive sets of signals or row vectors x.sup.T (t.sub.i) . . . provide the rows of a data matrix X comprising the receiver array output over a period of time. The required noise-reduced signal or residual for the kth array look direction corresponding to the ith set of signals is defined as e.sup.(k) (t.sub.i) (k=1,2 . . . ). Each of the residuals is generated by forming a respective linear combination of the ith set of antenna signals x.sup. T (t.sub.i) with a respective set of (complex) weighting coefficients expressed as a weight vector w.sup.(k) (i) in each case,
i.e. EQU e.sup.(k) (t.sub.i)=x.sup.T (t.sub.i)w.sup.(k) (i) (1)
The weight vector w.sup.(k) (i) for the kth direction is that calculated over all signals generated up to time t.sub.i, i.e. x.sup.T (t.sub.1), x.sup.T (t.sub.2), . . . x.sup.T (t.sub.i) which form the data matrix of i rows X(i). The weight vector w.sup.(k) (i) is that which minimize .vertline..vertline.X(i)w.sup.(k) (i).vertline..vertline. subject to a linear constraint of the form: EQU c.sup.(k)T w.sup.(k) (i)=.mu..sup.(k) ( 2)
Equation (2) defines the set of constraint vectors c.sup.(k)T (k=1,2, . . . ) which in turn define the required array look directions. It imposes the condition that the product of the kth weight vector and the kth constraint must yield a constant value .mu..sup.(k) corresponding to the receiver array gain in the kth look direction. Equations (1) and (2) collectively define the MVDR problem of simultaneously calculating noise-reduced signal residuals e.sup.(k) (t.sub.i) by weighting subject to constraint vectors c.sup.(k)T defining selected look directions (or other preconditions for applications outside the direction-finding field).
The prior art does not provide a processor capable of generating MVDR residuals from an array of sensors. At best, it requires a plurality of processors, one for each look direction. British Patent No. 2,151,378B describes a systolic array processor for computing residuals without constraints for a related but different problem. It treats the case of a main antenna generating successive signals of the kind y(t.sub.i) (or y.sub.i) and associated auxiliary antennas generating successive sets of signals x.sup.T (t.sub.i), mathematical nomenclature having been altered for conformity with the preceding discussion. The approach is to carry out a QR decomposition of the data matrix X(i) of auxiliary antenna signals. The QR decomposition process is described in the prior art by Gentleman and Kung, "Matrix triangularisation by systolic arrays", Proc. SPIE, Vol. 298, Real Time Signal Processing IV (1981). It involves the use of a triangular systolic array processor to triangularise the data matrix X(i), the array incorporating boundary cells along its major diagonal together with above-diagonal internal cells. The boundary cells compute rotation parameters from input data and the internal cells apply them to input data. In consequence, the data matrix X(i) becomes transformed to a triangular matrix R by operation of the rotation matrix Q comprising the rotation parameters. The rotation parameters are then employed to rotate or transform successive main antenna signals y(t.sub.i), and the resulting cumulatively rotated versions of y(t.sub.i) are multiplied by cumulatively multiplied cosine rotation parameters to provide the required residuals. The residuals take the form of x.sup.T (t.sub.i)w(i)+y(t.sub.i); i.e. a weighted linear combination of the auxiliary antenna signals is formed with the object of cancelling out unwanted noise contributions contained in the main antenna signal y(t.sub.i). The weight vector w(i) is however not subject to any constraint. Moreover, in many important array signal processing applications, there is no main antenna or other sensor. All receivers of a typical array are equivalent. It is therefore inappropriate to arbitrarily designate one receiver as a main receiver and the remainder as auxiliaries, particularly since failure of the designated main receiver renders signal processing inoperative. It is a requirement of array signal processing that it should degrade gracefully. Progressive in-service failure of individual receivers in an array should not produce sudden catastrophic loss of output from the whole array.
British Patent No. 2,143,378B (U.S. Pat. No. 4,688,187) discloses a processor for the application of one or more constraints to sets of signals from a sensor array or the like. Here again the approach involves designating one sensor signal as a main signal and signals from other array sensors as auxiliaries. The required constraint vector is introduced by subtracting from each auxiliary signal the product of the main signal with a respective constraint coefficient. To introduce multiple constraints in combination, i.e. to apply a constraint matrix, this procedure is repeated in one or more subsequent processors. After introduction of the constraint or constraints, signal residuals may be obtained by passing signals output from the processor to a device in accordance with British Patent No. 2,151,378B previously mentioned.
The use of a constraint matrix or simultaneously applied multiple constraints is also described by McWhirter and Shepherd in "A systolic array for linearly constrained least-squares problems", Proc. SPIE, Vol. 696, Advanced Algorithms and Architectures for Signal Processing (1986). This discloses a systolic array having a constraint pre-processing section coupled to a residual extraction section.
It also dispenses with the requirement for one main signal distinct from auxiliaries, all signals being treated equivalently. It is capable of applying a plurality of constraint vectors in combination, i.e. a constraint matrix. However, in order to deal with the MVDR problem, it is necessary to apply a plurality of constraints separately and produce respective residuals for each constraint independently. To achieve this employing the prior art of McWhirter and Sherpherd requires a separate processor for each constraint. Each processor would comprise a constraint application section coupled to a residual extraction section. Such a multiplicity of processors is undesirably complex and expensive.
The MVDR problem has been analysed mathematically by R. Schreiber, in "Implementation of adaptive array algorithms", IEEE Trans., Vol. ASSP-34, No. 5, p. 1038 (1986). Schreiber provides an algorithm involving steps each of which appears to be implementable on some (undisclosed) form of systolic array. However, the algorithm as a whole appears to be incompatible with prior art systolic array design. One step in Schreiber's algorithm (triangular matrix update) would require each input data vector to be passed downwards from the top row of a triangular processor array to the bottom at the rate of one processor row per clock cycle. Another step (the back substitution process) would require the same vector of data to be passed upwards through the same array at the rate of one row per clock cycle. Both steps must be completed before the next data vector is input to the top row of the array. This requires of the order of m clock cycles, where m is the number of signal channels, and the throughput rate and efficiency of the array is greatly reduced as a result.
Bojanczyk and Luk describe an MVDR beamforming algorithm in Proc. SPIE, Vol. 826, Advanced Algorithms and Architectures for Signal Processing II (1987). Like McWhirter and Shepherd, their approach requires a respective preprocessing operation to be applied to sensor array signals for each of the required MVDR constraints. Consequently, the arithmetic operations required correspond to one processor per constraint as discussed earlier.